public class FindMedianFromDataStream {
    PriorityQueue<Integer> largeHeap;
    PriorityQueue<Integer> smallHeap;

    public FindMedianFromDataStream() {
        largeHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
        smallHeap = new PriorityQueue<>();
    }

    // 1.m == n
    // 2.m == n+1
    public void addNum(int num) {
        int m = largeHeap.size();
        int n = smallHeap.size();
        if(m == 0) {
            largeHeap.offer(num);
            return;
        }

        int x = largeHeap.peek();
        if(m == n) {
            if(num <= x) {
                largeHeap.offer(num);
            }else {
                // num > x
                smallHeap.offer(num);
                largeHeap.offer(smallHeap.poll());
            }
        }else {
            if(num <= x) {
                largeHeap.offer(num);
                smallHeap.offer(largeHeap.poll());
            }else {
                // nums > x
                smallHeap.offer(num);
            }
        }
    }

    public double findMedian() {
        int m = largeHeap.size(), n = smallHeap.size();
        if(m == n) {
            return (largeHeap.peek() + smallHeap.peek()) / 2.0;
        }else {
            return largeHeap.peek();
        }
    }
}
